\documentclass[12pt,a4paper,french]{article}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage{a4}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{framed}
\usepackage{dsfont}
\usepackage[amsmath,thmmarks,thref,framed]{ntheorem}
\usepackage[dvips]{graphics}
\usepackage{epsfig}
\usepackage{calc}
\usepackage{tabls}
\usepackage{slashbox}
\usepackage{times}
\usepackage{multicol}
\usepackage{tabularx}
\usepackage{textcomp}
\usepackage{pst-all}
\usepackage[a4paper]{geometry}
\input{symboles.sty}

\geometry{hmargin=1cm, vmargin=1.5cm}
\title{Département d'informatique, partiel de Mathématiques discrètes\\  
Semestre 2, juin 2010, 3 heures.\\ 
}

\date{}

\begin{document}
\vspace{-7em}
\maketitle
\vspace{-5em}

\noindent Seule une fiche manuscrite RV de format A5 est autorisée. 

\section{QCM}
Vous aurez +1 à chaque valeur de vérité trouvée, -1 à chaque erreur (et 0 en absence de réponse). Les notes seront ajustées à l'intervalle $[0;20]$ \\


Q. 1. La négation de 
$(\forall x \, . \, p(x) \Rightarrow q(x))$ est 
$\exists x \, . \, p(x) \land \neg q(x)$.
 L'assertion proposée est vraie ou fausse?
   

Q. 2. 
Soit $P$, $Q$ et $R$ des variables propositionnelles.
La formule $P \land (\neg P \lor R) \land Q $ est en CNF.
L'assertion proposée est vraie ou fausse ? 

Q. 3. 
Soit $x$ et $y$ des entiers naturels.
$\forall x \, .\, (\exists y \, .\, x +y \ge x +1 )$
est vraie.
L'assertion proposée est vraie ou fausse ? 

Q. 4. 
Dans la formule
$(\forall x \, . \, x \ge 5) \land (\exists y \, . \, y \ge x)$
toutes les occurrences de la variable $x$ sont liées.
L'assertion proposée est vraie ou fausse ? 

Q. 5. 
Soit \textit{dodec} le prédicat unaire qui est vrai si son paramètre est un dodécaèdre, 
\textit{cube} le prédicat unaire qui est vrai si son paramètre est un cube, 
\textit{petit} le prédicat unaire qui est vrai si son paramètre est petit,
\textit{entre} le prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième
et 
\textit{devant} le prédicat binaire qui est vrai si son premier paramètre est devant son second paramètre. 

Les formules
$
\exists x \, .\, dodec(x) \land petit(x) \textrm{ et } 
\exists x \, .\, dodec(x) \Rightarrow petit(x)
$
n'ont jamais la même valeur de vérité.
 L'assertion proposée est vraie ou fausse?
   

Q. 6. 
Une formule propositionnelle est en CNF
si elle est exprimée comme une conjonction de formules.
L'assertion proposée est vraie ou fausse ? 

Q. 7. La formule
$\forall x\,.\, (\exists y\,.\, p(x) \land p(y))$ est équivalente à 
$\forall y\,.\, (\exists x\,.\, p(y) \land p(x))$.
 L'assertion proposée est vraie ou fausse?
   

Q. 8. 
Soit \textit{dodec} le prédicat unaire qui est vrai si son paramètre est un dodécaèdre, 
\textit{cube} le prédicat unaire qui est vrai si son paramètre est un cube, 
\textit{petit} le prédicat unaire qui est vrai si son paramètre est petit,
\textit{entre} le prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième
et 
\textit{devant} le prédicat binaire qui est vrai si son premier paramètre est devant son second paramètre. 
Dans la formule suivante toutes les occurrences de $x$ sont liées.
$
\forall x \, . \, 
\textit{dodec}(x) \lor  devant(x, y) \Rightarrow 
(
(\exists y \, .\, cube(y) \land \neg devant(x, y)) 
\land  entre(u,y,x)
).
$
 L'assertion proposée est vraie ou fausse?
   

Q. 9. 
Dans la formule
$P(a) \Rightarrow Q(a)$ toutes les occurrences de 
la variable $a$ ne sont pas liées.
L'assertion proposée est vraie ou fausse ? 

Q. 10. 
Soit $p(x)$ et $r(x)$ deux prédicats unaires. Une forme prénexe de 
$\exists x \,.\, p(x) \land (\forall y \,.\, p(y) \Rightarrow r(x))$ est 
$\exists x\,.\, \forall y \, . \, p(x) \land (\neg p(y) \lor r(x))$.
L'assertion proposée est vraie ou fausse ? 

Q. 11. 
   
Une \emph{clause propositionnelle} est une disjonction de proposition. 
L'assertion proposée est vraie ou fausse ? 
 

Q. 12. 
Soit $P$, $Q$ et $R$ des variables propositionnelles.
La mise en forme CNF de la formule 
$P \land Q \Rightarrow R$ est $\{\neg P \lor \neg Q \lor  R\}$.
L'assertion proposée est vraie ou fausse ? 

Q. 13. On se donne les prédicats suivants avec leur signification:
$g(x)$ si et seulement si $x$ est un gourmet, 
$n(x)$ si et seulement si $x$ est généreux, 
$o(x)$ si et seulement si $x$ est mon oncle.
\og Des gourmets manquent de générosité \fg{} peut se représenter par $\forall x \, .\, g(x) \land \neg n(x)$.
L'assertion proposée est vraie ou fausse ? 

Q. 14. On se donne les prédicats suivants avec leur signification:
$g(x)$ si et seulement si $x$ est un gourmet, 
$n(x)$ si et seulement si $x$ est généreux, 
$o(x)$ si et seulement si $x$ est mon oncle.
\og Mes oncles sont généreux \fg{} peut se représenter par $\exists x \, .\, g(x) \land n(x)$.
L'assertion proposée est vraie ou fausse ? 

Q. 15. 
Une \emph{clause propositionnelle} est une disjonction de variables 
propositionnelles éventuellement niées. 
L'assertion proposée est vraie ou fausse ? 

Q. 16. Si j'étudie, je n'échoue pas en maths,
si je ne joue pas au basket-ball, alors j'étudie,
mais j'ai échoué en mathématiques.
Donc, j'ai joué au basket-ball.
 Le raisonnement proposé est-il incorrect?
         

Q. 17. On considère les prédicats et constantes suivants avec leur interprétation sur un univers constitué d'individus humains.

\begin{center}
\begin{tabular}{|r|l|}
\hline
 prédicat & sens \\
\hline
$\textit{aime}(x,y)$                 & $x$ aime $y$ \\
$\textit{maries}(x,y)$                & $x$ et $y$ sont mariés  \\
$\textit{femme}(x)$                  & $x$ est une femme \\
$\textit{homme}(x)$                  & $x$ est un  homme \\
$\textit{fidele}(x)$                 & $x$ est fidèle \\
$\textit{honete}(x)$                 & $x$ dit la vérité \\
$a$                                  & Alice \\
$b$                                  & Bob \\
$c$                                  & Clinton \\
\hline
\end{tabular}
\end{center}

\og Chaque époux aime son épouse et réciproquement \fg{} peut se  traduire en
$
\forall x,y \, . \,
(\textit{homme}(x) \land
\textit{femme}(y) \land
\textit{maries}(x,y)) \Rightarrow
(\textit{aime}(x,y) \land
\textit{aime}(y,x))
$.
L'assertion proposée est vraie ou fausse ? 

Q. 18. La négation de 
$(\forall x \, . \, p(x) \Rightarrow q(x))$ est 
$\exists x \, . \, \neg p(x) \Rightarrow \neg q(x)$.
 L'assertion proposée est vraie ou fausse?
   

Q. 19. On se donne les prédicats suivants avec leur signification:
$g(x)$ si et seulement si $x$ est un gourmet, 
$n(x)$ si et seulement si $x$ est généreux, 
$o(x)$ si et seulement si $x$ est mon oncle.
\og Des gourmets manquent de générosité \fg{} peut se représenter par $\forall x \, .\, g(x) \Rightarrow \neg n(x)$.
L'assertion proposée est vraie ou fausse ? 

Q. 20. 
Soit $a$ et $b$ des symboles de constante,
$f$ un symbole de fonction unaire,
$g$ un symbole de fonction binaire et
$S$ un symbole de relation binaire. 
L'expression $g(a,f(b))$ contient quatre termes.
 L'assertion proposée est vraie ou fausse ?
   

Q. 21. 
La négation de 
$(\exists y \, . \, p(y) \land \neg q(y))$ est 
$(\forall y \, . \, \neg p(y) \lor \neg   q(y))$.
 L'assertion proposée est vraie ou fausse?

Q. 22. On se donne les prédicats suivants avec leur signification:
$g(x)$ si et seulement si $x$ est un gourmet, 
$n(x)$ si et seulement si $x$ est généreux, 
$o(x)$ si et seulement si $x$ est mon oncle.
\og Certains de mes oncles ne sont pas gourmets \fg{} peut se représenter par $\forall x \, .\, o(x) \Rightarrow \neg g(x)$.
L'assertion proposée est vraie ou fausse ? 

Q. 23.  On considère la proposition 
$$
  (A \Rightarrow B) \Rightarrow 
  ((A \Rightarrow C) \Rightarrow (A \Rightarrow B \land C))
$$
Il existe une démonstration syntaxique sous hypothèses 
  qui prouve que cette proposition est un théorème. L'assertion proposée est vraie ou fausse ?
 

Q. 24. 
Une \emph{clause propositionnelle} est une conjonction de variables 
propositionnelles éventuellement niées. 
L'assertion proposée est vraie ou fausse ? 

Q. 25. 

Soit $p(x)$ et $q(x)$ deux prédicats unaires. Une forme prénexe de 
$(\forall x \,.\, p(x)) \Rightarrow \exists x \,.\, q(x)$ est 
$\forall x\,.\, (\exists x  \, . \, p(x) \Rightarrow q(x))$.
L'assertion proposée est vraie ou fausse ? 

 

Q. 26. 
Soit $p(x)$ et $q(x)$ deux prédicats unaires. Une forme prénexe de 
$(\forall x \,.\, p(x)) \Rightarrow \exists x \,.\, q(x)$ est 
$\exists x \, . \, \neg p(x) \lor q(x)$.
L'assertion proposée est vraie ou fausse ? 

Q. 27. 
Soit $P$, $Q$ et $R$ des variables propositionnelles.
La mise en forme CNF de la formule 
$(P \Rightarrow Q) \land (P \Rightarrow R)$ est $\{\neg P \lor Q , \neg P \lor R\}$.
L'assertion proposée est vraie ou fausse ? 

Q. 28. Si je travaille, je ne peux pas étudier;
Soit je travaille, soit je suis reçu en mathématiques;
j'ai été reçu en mathématiques.
Donc j'ai étudié.
 Le raisonnement proposé est-il incorrect?
         

Q. 29. Dans la formule
$(\forall x\,.\, p(x) \Rightarrow q(x)) \land r(y)$, la variable 
$x$ admet une occurrence libre.
 L'assertion proposée est vraie ou fausse?
   

Q. 30. La négation de 
$(\exists y \, . \, p(y) \land \neg q(y))$ est 
$(\forall y \, . \, \neg p(y) \lor  q(y))$.
 L'assertion proposée est vraie ou fausse?
   

Q. 31. La formule
$\forall x \,.\, x > 0 \Rightarrow
  (\exists y \, . \, e^y = x )
$
est vraie sur l'univers $\mathds{R}$.
L'assertion proposée est vraie ou fausse ? 

Q. 32. 
Soit $p(x)$ et $r(x)$ deux prédicats unaires. Une forme prénexe de 
$\forall x \,.\, (\forall y \,.\, p(y)) \Rightarrow r(x)$ est 
$\forall x, y  \, . \, p(y) \lor \neg r(x)$.
L'assertion proposée est vraie ou fausse ? 

Q. 33. 
Un ensemble de clauses est contradictoire par résolution s'il existe une paire de clauses 
dont la résolvante est la clause vide.
L'assertion proposée est vraie ou fausse ? 

Q. 34. 
Les formules $P\lor \neg Q \lor R$ et $ \neg P \lor Q \lor \neg R$ sont résolubles.
L'assertion proposée est vraie ou fausse ? 

Q. 35. Soit $p(x)$ le prédicat unaire qui est vrai si et seulement
si le paramètre $x$ est pair. 
La formule 
$
(\exists x \, . \, p(x))
\Rightarrow 
(\forall x \, . \, p(x))
$ est vraie sur l'univers $\{1 \}$.   
L'assertion proposée est vraie ou fausse? 

Q. 36. 
Soit $P$, $Q$ et $R$ des variables propositionnelles.
La mise en forme CNF de la formule 
$P \Rightarrow (Q \land R)$ est $\{\neg P \lor Q ,R\}$ .
L'assertion proposée est vraie ou fausse ? 

Q. 37.  Soit $P$, $Q$ et $R$ des variables propositionnelles.
La formule 
$ P \lor Q \lor \neg R$  
est une clause propositionnelle.
L'assertion proposée est vraie ou fausse ? 

Q. 38. 
Soit \textit{dodec} le prédicat unaire qui est vrai si son paramètre est un dodécaèdre, 
\textit{cube} le prédicat unaire qui est vrai si son paramètre est un cube, 
\textit{petit} le prédicat unaire qui est vrai si son paramètre est petit,
\textit{entre} le prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième
et 
\textit{devant} le prédicat binaire qui est vrai si son premier paramètre est devant son second paramètre. 
\og les seuls grands cubes sont b et c \fg{} peut-elle se traduire en 
$
\forall x \, .\, 
(\neg petit(x) \land cube(x)) 
\leftrightarrow 
 ( x = b \lor  x = c).
$
 L'assertion proposée est vraie ou fausse?
   

Q. 39. 
Les formules $P\lor \neg Q \lor R$ et $ P \lor  Q$ sont résolubles.
L'assertion proposée est vraie ou fausse ? 

Q. 40. 
Si la saturation de la résolution engendre la clause vide, alors l'ensemble de clauses est satisfaisable.
L'assertion proposée est vraie ou fausse ? 

% Q. 41. On se donne les prédicats suivants avec leur signification:
% $g(x)$ si et seulement si $x$ est un gourmet, 
% $n(x)$ si et seulement si $x$ est généreux, 
% $o(x)$ si et seulement si $x$ est mon oncle.
% \og Des gourmets manquent de générosité \fg{} peut se représenter par $\exists x \, .\, g(x) \land \neg n(x)$.
% L'assertion proposée est vraie ou fausse ? 

% Q. 42. La négation de 
% $(\exists y \, . \, p(y) \land \neg q(y))$ est 
% $(\forall y \, . \, p(y) \Rightarrow  q(y))$.
%  L'assertion proposée est vraie ou fausse?
   

% Q. 43. 
% Une formule propositionnelle est en (CNF)
% si elle est exprimée comme une disjonction de clauses.
% L'assertion proposée est vraie ou fausse ? 

% Q. 44. On considère les prédicats et constantes suivants avec leur interprétation sur un univers constitué d'individus humains.

% \begin{center}
% \begin{tabular}{|r|l|}
% \hline
%  prédicat & sens \\
% \hline
% $\textit{aime}(x,y)$                 & $x$ aime $y$ \\
% $\textit{maries}(x,y)$                & $x$ et $y$ sont mariés  \\
% $\textit{femme}(x)$                  & $x$ est une femme \\
% $\textit{homme}(x)$                  & $x$ est un  homme \\
% $\textit{fidele}(x)$                 & $x$ est fidèle \\
% $\textit{honete}(x)$                 & $x$ dit la vérité \\
% $a$                                  & Alice \\
% $b$                                  & Bob \\
% $c$                                  & Clinton \\
% \hline
% \end{tabular}
% \end{center}

% \og L'époux qui aime son épouse lui est fidèle \fg{} peut se traduire en
% $
% \forall x,y \, . \,
% \textit{homme}(x) \land
% \textit{femme}(y) \land
% \textit{maries}(x,y) \land
% \textit{aime}(x,y) \land
% \textit{aime}(y,x)
% $.
% L'assertion proposée est vraie ou fausse ? 

% Q. 45. 
% Soit $P$, $Q$ et $R$ des variables propositionnelles.
% La mise en forme CNF de la formule 
% $P \land Q \Rightarrow R$ est $\{\neg P, \neg Q, R\}$ .
% L'assertion proposée est vraie ou fausse ? 

% Q. 46.  Soit $P$, $Q$ et $R$ des variables propositionnelles.
% La formule 
% $ P \lor Q \lor (P \land \neg R)$
% est une clause propositionnelle.
% L'assertion proposée est vraie ou fausse ? 

% Q. 47. La relation $\{P,Q\} \vdash R$   se lit-elle
% \og $R$ est une conséquence logique de l'ensemble
%                      $\{P,Q\}$ \fg{}?
                      

\section*{Réponses au QCM}
\begin{Large}
\begin{center}
\begin{tabular}{|l|c|c||l|c|c||l|c|c|}
\hline
Numéro & V & F & Numéro & V & F & Numéro & V & F \\ 
\hline
Q. 1 & &  & Q. 2 & &  & Q. 3 & &  \\ 
\hline
Q. 4 & &  & Q. 5 & &  & Q. 6 & &  \\ 
\hline
Q. 7 & &  & Q. 8 & &  & Q. 9 & &  \\ 
\hline
Q. 10 & &  & Q. 11 & &  & Q. 12 & &  \\ 
\hline
Q. 13 & &  & Q. 14 & &  & Q. 15 & &  \\ 
\hline
Q. 16 & &  & Q. 17 & &  & Q. 18 & &  \\ 
\hline
Q. 19 & &  & Q. 20 & &  & Q. 21 & &  \\ 
\hline
Q. 22 & &  & Q. 23 & &  & Q. 24 & &  \\ 
\hline
Q. 25 & &  & Q. 26 & &  & Q. 27 & &  \\ 
\hline
Q. 28 & &  & Q. 29 & &  & Q. 30 & &  \\ 
\hline
Q. 31 & &  & Q. 32 & &  & Q. 33 & &  \\ 
\hline
Q. 34 & &  & Q. 35 & &  & Q. 36 & &  \\ 
\hline
Q. 37 & &  & Q. 38 & &  & Q. 39 & &  \\ 
\hline
Q. 40 & &  &  & &  &  & &  \\ 
\hline
\end{tabular}
\end{center}
\end{Large}
\section{Raisonnement}

\subsection{Preuve syntaxique par résolution}
Effectuer la preuve syntaxique suivante par résolution:
$$
\left\{
A \Rightarrow B \lor C,
D \Rightarrow A,
B \Rightarrow \neg D\right\}
\big) \vdash
D \Rightarrow C
$$

\subsection{L'Île de Puro Pira}
L'île de Puro Pira est peuplée 
de \emph{Purs} qui disent toujours la vérité et de 
de \emph{Pires} qui ne disent que des mensonges.

Débarqué sur l'île, l'anthropologue Abercrombie rencontre trois indigènes Alice, Bernard et Chloé.
\begin{enumerate}
\item\label{item1} Alice affirme \og C’est moi le chef\fg{}. 
\item\label{item2} Bernard affirme aussi \og C’est moi le chef\fg{}. 
\item Quant à Chloé elle ajoute \og Au plus l’un de nous trois dit la vérité.\fg{}
\end{enumerate}
On sait qu'il n'y a qu'un seul chef.

Par la suite 
\begin{itemize}
\item $A$, $B$ et $C$ sont les variables propositionnelles qui valent chacune 
  vrai si et seulement si $A$ est un pur,   $B$ est un pur et $C$ est un pur respectivement; 
\item $Ac$, $Bc$ et $Cc$ sont les variables propositionnelles qui 
  valent chacune vrai si et seulement si $Ac$ est un chef,   $Bc$ est un chef
  et $Cc$ est un chef respectivement; 
\end{itemize}


\begin{enumerate}
\item Montrer que l'affirmation \og il n'y a qu'un seul chef \fg{} 
  peut se représenter par la formule 
  $$ (Ac \lor Bc \lor Cc) \land 
  \neg (Ac \land Bc) \land \neg (Ac \land Cc) \land \neg (Bc \land Cc)
  $$ 
\item Montrer que l'affirmation de Chloé peut se représenter par la formule
  $$
  (C \Rightarrow \neg A \land \neg B ) \land
  (\neg C \Rightarrow A \land B ) 
  $$
\item Traduire en logique propositionnelle les propositions des 
  items~\ref{item1}. et~\ref{item2} relatives aux affirmations d'Alice et 
  Bernard.  
\item A l'aide de la méthode de résolution trouver le statut de chaque 
indigène.
\end{enumerate}  


\subsection{Problème Bonus}
 On considère les propositions suivantes:\par
\begin{enumerate}
\item  Tout crime a un auteur 
\item Seuls les gens malhonnêtes commettent des crimes 
\item  On n'arrête que les gens malhonnêtes 
\item  Les gens malhonnêtes arrêtés ne commettent pas de crimes 
\item  Des crimes se produisent 
\end{enumerate}

Montrer par la méthode de votre choix qu'il y a 
des gens malhonnêtes en liberté. 


\end{document}